package com.future;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Description: 952. 按公因数计算最大组件大小
 *
 * @author weiruibai.vendor
 * Date: 2022/7/8 14:46
 */
public class Solution_952 {

    public static void main(String[] args) {
        int[] nums = new int[]{4, 6, 15, 35};
        nums = new int[]{20, 50, 9, 63};
        //nums = new int[]{99, 100, 69, 39, 14, 56, 91, 60};
        // 32,69,28,9,44,86,14,15,54,23,57,27,60
        nums = new int[]{32, 69, 28, 9, 44, 86, 14, 15, 54, 23, 57, 27, 60};
        System.out.println(largestComponentSize(nums));
    }

    /**
     *
     * @param nums
     * @return
     */
    public static int largestComponentSize(int[] nums) {
        Info info = new Info(nums);
        return info.getAns();
    }

    private static class Info {

        Map<Integer, Node> factoryNode;
        private Map<Integer, Node> keyNode;

        public int ans;

        public Info(int[] nums) {
            ans = 1;
            keyNode = new HashMap<>();
            factoryNode = new HashMap<>();

            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                Node node = new Node(1, num);
                keyNode.put(num, node);
            }
            doWork(nums);
        }

        public void doWork(int[] nums) {
            for (int i = 0; i < nums.length; i++) {
                int num = nums[i];
                int limit = (int) Math.sqrt(num);
                for (int j = 1; j <= limit; j++) {
                    if (num % j == 0) {
                        if (j != 1) {
                            if (factoryNode.containsKey(j)) {
                                union(factoryNode.get(j), keyNode.get(num));
                            } else {
                                factoryNode.put(j, keyNode.get(num));
                            }
                        }
                        int other = num / j;
                        if (factoryNode.containsKey(other)) {
                            union(factoryNode.get(other), keyNode.get(num));
                        } else {
                            factoryNode.put(other, keyNode.get(num));
                        }
                    }
                }
            }


        }

        private void union(Node node1, Node node2) {
            Node f1 = findFather(node1);
            Node f2 = findFather(node2);
            if (f1 != f2) {
                int f1Size = f1.size;
                int f2Size = f2.size;
                int newSize = f1Size + f2Size;
                if (f1Size >= f2Size) {
                    node2.father = f1;
                    node2.size = 1;
                    f2.size = 1;
                    f2.father = f1;
                    f1.size = newSize;
                } else {
                    node1.father = f2;
                    node1.size = 1;
                    node1.father = f2;
                    f1.father = f2;
                    f2.size = newSize;
                }
                ans = Math.max(ans, newSize);
            }
        }

        public int getAns() {
            return ans;
        }

        private Node findFather(Node node) {
            List<Node> tmp = new ArrayList<>();
            while (node != node.father) {
                tmp.add(node);
                node = node.father;
            }
            // 剪枝(记得在这里做，否则超时)
            for (Node n : tmp) {
                n.father = node;
            }
            return node;
        }
    }

    private static class Node {
        public int size; //大小

        public int value; // 当前节点值

        public Node father;// 当前节点父节点（value=father.value说明是自己就是父节点）

        public Node(int size, int value) {
            this.size = size;
            this.value = value;
            this.father = this;// 自己是自己的父类
        }

        public Node(int size) {
            this.size = size;
        }

        public Node() {
        }

        @Override
        public String toString() {
            return "Node{" +
                    "size=" + size +
                    ", value=" + value +
                    ", father=" + father.value +
                    '}';
        }
    }
}
